module Queue where

import qualified SlowQueue as Slow
import Debug.QuickCheck

------------------------------------------------------------------

empty   :: Q a
add     :: a -> Q a -> Q a
remove  :: Q a -> Q a
front   :: Q a -> a
isEmpty :: Q a -> Bool

------------------------------------------------------------------

data Q a = Q [a] [a]
  deriving (Eq, Show)
  
empty                     = Q [] []
--add x (Q front back)      = fixQ (Q front (x:back))
add x (Q front back)      = Q front (x:back)
remove (Q (x:front) back) = fixQ (Q front back)
front (Q (x:front) back)  = x
isEmpty (Q front back)    = null front && null back
  
------------------------------------------------------------------

fixQ :: Q a -> Q a
fixQ (Q [] back) = Q (reverse back) []
fixQ q           = q

------------------------------------------------------------------

instance Arbitrary a => Arbitrary (Q a) where
  arbitrary =
    do front <- arbitrary
       back  <- arbitrary
       return (Q front (if null front then [] else back))

------------------------------------------------------------------

contents :: Q Int -> Slow.Q Int
contents (Q front back) = Slow.Q (front ++ reverse back)

invariant :: Q Int -> Bool
invariant (Q front back) = not (null front && not (null back))

------------------------------------------------------------------

prop_Invariant q =
  invariant q

------------------------------------------------------------------

prop_Empty =
  contents empty == Slow.empty

prop_Add x q =
  contents (add x q) == Slow.add x (contents q)

prop_Remove q =
  not (isEmpty q) ==>
    contents (remove q) == Slow.remove (contents q)
      
prop_Front q = 
  not (isEmpty q) ==>
    front q == Slow.front (contents q)

prop_IsEmpty q =
  isEmpty q == Slow.isEmpty (contents q)

------------------------------------------------------------------

prop_Empty_Inv =
  invariant empty

prop_Add_Inv x q =
  invariant (add x q)

prop_Remove_Inv q =
  not (isEmpty q) ==> 
    invariant (remove q)

------------------------------------------------------------------

